package algorithms.que14;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * @功能
 * @创建时间 2020/9/7
 */
public class Sum3 {
    /*A+B=k问题---由于已排序,所以 k-A(1)=B(1)>k-A(2)=B(2)
     * 因此可以建立first和last分别指向首和尾
     * 以下方式不包括重复情况
     * */
    public static int twoSumFaster(int[] a,int k,int i)
    {
        int first=i,last=a.length-1;
        int cnt=0;
        while(first<last)
        {
            if(a[first]+a[last]<k)
                first++;
            else if(a[first]+a[last]>k)
                last--;
            else
            {
                cnt++;
                while(first<last&&a[first]==a[++first]);
                while(last>first&&a[last]==a[--last]);
            }
        }
        return cnt;
    }
    /*A+B+C=0   借鉴twoSumFaster.  B+C=-A便可  即令k=-A带入
     * */
    public static int threeSumFaster(int[] a)
    {
        int cnt=0;
        for(int i=0;i<a.length-1;i++)
        {
            int k=-a[i];
            cnt+=twoSumFaster(a, k, i+1);
        }
        return cnt;
    }


    public static void main(String[] args)
    {
        @SuppressWarnings("deprecation")
        int[] a= In.readInts("input.txt");
        Arrays.sort(a);
        StdOut.println(Arrays.toString(a));
        StdOut.println(twoSumFaster(a,0,0));
        StdOut.println(threeSumFaster(a));
    }
    public static int twoSumFaster(int[] a)
    {
        int pos=0,neg;
        int N=a.length;
        int cnt=0;
        for(int i=0;i<N;i++)    //找出第一个出现的正数,将数组分为正负两部分
        {
            if(a[i]>=0){ pos=i; break;}
        }
        neg=pos-1;
        for(int i=0;i<N;i++)
        {
            if(pos>=N||neg<0)   //正负两部分中有一个已达到临界
                break;
            if(a[pos]+a[neg]<0)    //正数绝对值小情况
                pos++;
            else if(a[pos]+a[neg]>0)  //正数绝对值大情况
                neg--;
            else                       //相等情况---涉及多组相等,用到排列组合方法
            {
                int samePos=0;int sameNeg=0;
                int temp=pos;
                while(pos<N&&a[pos]==a[temp])
                {    samePos++;pos++;}       //其中的pos++不能写到a[pos++]中--因为循环会多加一次
                temp=neg;
                while(neg>=0&&a[neg]==a[temp])
                {    sameNeg++;neg--;}
                cnt=cnt+(samePos*sameNeg);
            }
        }
        return cnt;
    }

//    public static void main(String[] args)
//    {
//        @SuppressWarnings("deprecation")
//        int[] a=In.readInts("input.txt");
//        Arrays.sort(a);
//        StdOut.println(Arrays.toString(a));
//        StdOut.println(twoSumFaster(a));
//    }
}
